//1.笨方法
//对于每个 i（从 1 到 n），考虑所有可能的完全平方数 j²（其中 j² ≤ i），则 i 可以拆分为 j² + (i - j²)。因此 dp[i] = min(dp[i], dp[i - j²] + 1)
class Solution {
public:
    int numSquares(int n) {
        static const int m = 1e4+10;
        vector<int> dp(m,10000);
        dp[0]=0;
        for(int i = 1; i <= n; ++i ) {
            for(int j=1;j*j<=i;++j) {
                dp[i] = min(dp[i], dp[i-j*j] + 1);
            }
            
        }
        return dp[n];
    }
};

//2.不要数组，减少空间复杂度------四平方和定理
class Solution {
public:
    // 判断是否为完全平方数
    bool isPerfectSquare(int x) {
        int y = sqrt(x);
        return y * y == x;
    }

    // 判断是否能表示为 4^k*(8m+7)
    bool checkAnswer4(int x) {
        while (x % 4 == 0) {
            x /= 4;
        }
        return x % 8 == 7;
    }

    int numSquares(int n) {
        if (isPerfectSquare(n)) {
            return 1;
        }
        if (checkAnswer4(n)) {
            return 4;
        }
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }
        return 3;
    }
};




